package com.shuang.dp23;




// Definition for a binary tree node.
 class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;

       TreeNode() {}

       TreeNode(int val) { this.val = val; }

       TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;this.right = right;
      }
  }
class Solution {
    //由dp数组状态标记递归 dp数组大小为2 dp[0]代表不偷当前节点的最大金额 dp[1]代表偷当前节点的最大金额
    public int rob(TreeNode root) {

        //递归实现 返回dp数组
        int[] res = robAction(root);

        return Math.max(res[0], res[1]);
    }

    private int[] robAction(TreeNode root) {

        int[] dp = new int[2];

        //终止条件 到达叶子节点的下面的空 一定没有金额偷与不偷都是0
        if (root == null) {
            return dp;
        }

        //一定是后序遍历 当前节点要拿到左右节点的结果

        int[] left = robAction(root.left);

        int[] right = robAction(root.right);

        //中 
        //不偷该节点得到的金额 （要偷该节点的左右孩子 得取左右孩子的偷与不偷的金额最大值）
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        //偷该节点得到的金额 那么左右节点就不能偷
        dp[1] = root.val + left[0] + right[0];

        //返回数组
        return dp;
    }
}